package A一周刷爆LeetCode.A基础班.I暴力递归;

/**
 * @author wei.zhao
 * @description: N皇后
 * @date 2022年03月27日 10:09
 */
public class Code08_NQueens {

    public static int num1(int n) {
        if (n < 1) {
            return 0;
        }
        return process(new int[n], 0);
    }

    /**
     * record：记录填放的皇后，rNum：当前准备放的行
     */
    public static int process(int[] record, int rNum) {
        if (rNum == record.length) {
            return 1;
        }
        int result = 0;
        for (int i = 0; i < record.length; i++) {
            if (isValid(record, rNum, i)) {
                //当前位置可以放皇后
                record[rNum] = i;
                result += process(record, rNum + 1);
                //为什么不需要还原？
                //因为判断当前行、列能否放数据只判断之前的行数据情况。
            }
        }
        return result;
    }

    /**
     * record：记录填放的皇后，rNum：当前准备放的行，p：当前准备放的位置
     */
    public static boolean isValid(int[] record, int rNum, int p) {
        for (int i = 0; i < rNum; i++) {
            // 当前填放的行，与任意一行同列或与同斜边，返回false
            if (p == record[i] || Math.abs(rNum - i) == Math.abs(p - record[i])) {
                return false;
            }
        }
        return true;
    }

}
